package com.fjl.array.leetcode1329;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;

/**
 * @Description
 * @Author: 01195
 * @Date: 2025/3/13 15:53
 */
/*
矩阵对角线 是一条从矩阵最上面行或者最左侧列中的某个元素开始的对角线，沿右下方向一直到矩阵末尾的元素。例如，矩阵 mat 有 6 行 3 列，从 mat[2][0] 开始的 矩阵对角线 将会经过 mat[2][0]、mat[3][1] 和 mat[4][2] 。
给你一个 m * n 的整数矩阵 mat ，请你将同一条 矩阵对角线 上的元素按升序排序后，返回排好序的矩阵。
 */
public class Clazz {
    public int[][] diagonalSort(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        // 存储所有对角线的元素列表
        HashMap<Integer, ArrayList<Integer>> diagonals = new HashMap<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 横纵坐标之差可以作为一条对角线的 ID
                int diagonalID = i - j;
                diagonals.putIfAbsent(diagonalID, new ArrayList<>());
                diagonals.get(diagonalID).add(mat[i][j]);
            }
        }
        // 从数组末尾删除元素效率较高，所以我们把 ArrayList 倒序排序
        for (List<Integer> diagonal: diagonals.values()) {
            Collections.sort(diagonal, Collections.reverseOrder());
        }
        // 把排序结果回填二维矩阵
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ArrayList<Integer> diagonal = diagonals.get(i - j);
                mat[i][j] = diagonal.remove(diagonal.size() - 1);
            }
        }
        return mat;
    }
}
